package src.linkeLlist;

public class no234 {  //判断回文链表

    //转为数组判断
    public boolean isPalindrome1(ListNode head) {
        //先求链表长度，以此确定数组定多大，不然要数组扩容浪费空间
        int length = 0;
        ListNode p = head;
        while (p != null) {
            p = p.next;
            length++;
        }
        p = head;
        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            arr[i] = p.val;
            p = p.next;
        }
        for (int i = 0, j = length - 1; i < j; i++, j--) {
            if (arr[i] != arr[j]) return false;
        }
        return true;

    }

    //从链表中间断开，翻转切下来的后半段，再依次比较两个链表
    public boolean isPalindrome2(ListNode head) {
        //如果为空或者仅有一个节点，返回true
        if (head == null || head.next == null) return true;

        ListNode p = head, q = head;  //p走两步，q走一步，切开后q为后半段链表的头
        ListNode pre = head;  //pre为q的前一个结点，从pre处切开
        while (p != null && p.next != null) {  //记住这里，要让指针走两步，就这么判断
            pre = q;
            p = p.next.next;
            q = q.next;
        }
        pre.next = null;  //从pre结点切开链表

        ListNode p2 = no206.reverseList(q);
        ListNode p1 = head;
        while (p1 != null && p2 != null) {
            if (p1.val != p2.val) return false;
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;

    }
}
